package club.worldbang.structures.linkedList.seqList;

import club.worldbang.structures.linkedList.ISeqList;
//顺序表实现
public class SeqList<T> implements ISeqList<T> {

	private Object[] table; // 数组声明,用于存储元素
	private int length; // 顺序表的大小
	private static final int DEFAULR_CAPACITY = 64;//默认数组长度 

	//申请数组大小为capacity的空间
	public SeqList(int capacity) {
		// 申请数组存储空间,元素初始化为null
		this.table = new Object[Math.abs(capacity)];
		this.length = 0;
	}

	/**
	 * 默认大小为64
	 */
	public SeqList() {
		this(DEFAULR_CAPACITY);
	}

	/**
	 * 传入一个数组初始化顺序表
	 * 
	 * @param array
	 */
	public SeqList(T[] array) {
		if (array == null) {
			throw new NullPointerException("array can\'t be empty!");
		}
		// 创建对应容量的数组
		this.table = new Object[array.length];
		for (int i = 0; i < array.length; i++) {
			this.table[i] = array[i];
		}
		this.length = array.length;
	}

	/**
	 * 判断顺序表是否为空
	 */
	public boolean isEmpty() {
		return this.length == 0;
	}

	/**
	 * 计算顺序表的大小
	 */
	public int length() {
		return this.length;
	}

	/**
	 * 获取元素
	 * 从顺序表中获取值是一种相当简单的操作并且效率很高，这是由于顺序表内部采用了数组作为存储数据的容器。
	 * 因此只要根据传递的索引值，然后直接获取数组中相对应下标的值即可
	 */
	public T get(int index) {
		if (index >= 0 && index < this.length) {
			return (T) this.table[index];
		}
		return null;
	}

	/**
	 * 设置某个节点的值
	 * 在顺序表中替换值也是非常高效和简单的，只要根据传递的索引值index找到需要替换的元素，然后把对应元素值替换成传递的data值即可
	 */
	public T set(int index, T data) {
		if (index >= 0 && index < this.length && data != null) {
			T old = (T) this.table[index];
			this.table[index] = data;
			return old;
		}
		return null;
	}

	/**
	 * 指定位置index插入元素
	 * 在顺序表中执行插入操作时，如果其内部数组的容量尚未达到最大值时，可以归结为两种情况：
	 * 一种是在头部插入或者中间插入，这种情况下需要移动数组中的数据元素，效率较低；
	 * 另一种是在尾部插入，无需移动数组中的元素，效率高。
	 * 但是当顺序表内部数组的容量已达到最大值无法插入时，则需要申请另一个更大容量的数组并复制全部数组元素到新的数组，这样的时间和空间开销是比较大的，也就导致了效率更为糟糕了。
	 * 因此在插入频繁的场景下，顺序表的插入操作并不是理想的选择。
	 */
	public boolean add(int index, T data) {
		if (data == null) {
			return false;
		}
		// 插入下标容错判断,插入在最前面
		if (index < 0)
			index = 0;
		// 插入下标容错判断，插入在最后面
		if (index > this.length)
			index = this.length;
		// 判断内部数组是否已满
		if (this.length == table.length) {
			// 已满，则如下成倍扩容
			Object[] tmp = this.table;// 临时存储
			this.table = new Object[tmp.length * 2];// 成倍扩容
			// 复原临时存储至原来位置即先把原数组下标从0到index-1(即插入位置的前一个位置)复制到新数组
			for (int i = 0; i < tmp.length; i++) {
				this.table[i] = tmp[i];
			}
		}
		// 腾出位置，插入新元素
		// 从原数组的最后一个元素开始直到index位置，都往后一个位置（即，插入之后，下标都会+1）
		// 最终腾出的位置就是插入新元素的位置
		for (int j = this.length - 1; j >= index; j--) {
			this.table[j + 1] = this.table[j];
		}
		// 插入新值
		this.table[index] = data;
		// 顺序表大小+1
		this.length++;
		// 插入成功
		return true;
	}

	/**
	 * 直接在尾部插入元素
	 */
	public boolean add(T data) {
		return add(this.length, data);
	}

	/**
	 * 根据index移除元素（删除元素）
	 * 顺序表的删除操作和前的插入操作情况是类似的，
	 * 如果是在中间或者头部删除顺序表中的元素，那么在删除位置之后的元素都必须依次往前移动，效率较低，
	 * 如果是在顺序表的尾部直接删除的话，则无需移动元素，此情况下删除效率高。
	 */
	public T remove(int index) {
		if (this.length != 0 && index >= 0 && index <= this.length) {
			// 记录删除的元素，并后面返回
			T old = (T) this.table[index];
			// 从被删除的位置开始，后面的元素往前挪
			for (int j = index; j < this.length - 1; j++) {
				this.table[j] = this.table[j + 1];
			}
			// 挪结束后空出最后一个元素，设置其为空
			this.table[this.length - 1] = null;
			// 顺序表长度-1
			this.length--;
			return old;

		}
		return null;
	}

	/**
	 * 根据数据返回下标
	 * 要根据data在顺序表中查找第一个出现的数据元素的下标，只需要通过对比数据项是否相等，相等则返回下标，不相等则返回-1
	 */
	public int indexOf(T data) {
		if (data != null)
			for (int i = 0; i < this.length; i++) {
				// 相当则返回下标
				if (this.table[i].equals(data))
					return i;
			}
		return -1;
	}

	/**
	 * 直接删除数据
	 */
	public boolean remove(T data) {
		if (this.length != 0 && data != null) {
			return this.remove(this.indexOf(data)) != null;
		}
		return false;
	}
	
	/**
	 * 在顺序表中根据数据data找到需要删除的数据元素和前面分析的根据index删除顺序表中的数据元素是一样的道理，
	 * 因此我们只要通过比较找到与data相等的数据元素并获取其下标，
	 * 然后调用前面实现的remove(int index)方法来移除即可。
	 */
	public boolean removeAll(T data) {
		boolean done = false;
		if (this.length != 0 && data != null) {
			int i = 0;
			while (i < this.length) {
				// 找出数据相同的选项
				if (data.equals(this.table[i])) {
					this.remove(i);// 根据下标删除
					done = true;
				} else {
					i++;// 继续查找

				}
			}

		}
		return done;
	}

	/**
	 * 情况顺序表
	 */
	public void clear() {
		this.length = 0;
	}

	@Override
	public boolean equals(Object obj) {
		// 如果内存地址相当,那么两个顺序肯定相等
		if (this == obj) {
			return true;
		}

		// 判断是否属于同种类型对象
		if (obj instanceof SeqList) {
			// 强制转换成顺序表
			SeqList<T> list = (SeqList<T>) obj;
			for (int i = 0; i < this.length(); i++) {
				// 比较每个值是否相当
				if (!(this.get(i).equals(list.get(i)))) {
					return false;
				}
			}
			return true;
		}
		return false;
	}

	/**
	 * 查询是否包含某个数据
	 * 
	 * @param data
	 * @return
	 */
	public boolean contains(T data) {
		return this.indexOf(data) > 0;
	}

	/**
	 * 根据data查询最后一个出现在顺序表中的下标
	 * 
	 * @param data
	 * @return
	 */
	public int lastIndexOf(T data) {
		if (data != null) {
			for (int i = this.length - 1; i >= 0; i--) {
				if (data.equals(this.table[i])) {
					return i;
				}
			}

		}
		return -1;
	}

	@Override
	public String toString() {
		String str = "(";
		if (this.length != 0) {
			for (int i = 0; i < this.length - 1; i++)
				str += this.table[i].toString() + ", ";
			str += this.table[this.length - 1].toString();
		}
		return str + ") ";
	}
}
